Resource conflicts are a well-known problem in multiprocessing systems. In a multiprocessing system a plurality of data handling processes is executed concurrently. When the different processes need to access a main memory or other resources, a resource conflict may arise. Such a conflict must be resolved by allowing the accesses to proceed successively, causing some of the accesses to wait with the effect that the requesting process may have to wait as well.
Process timing is an important consideration in the resolution of access conflicts. In many applications real-time requirements are imposed on processes, which means that the processes need to complete, or perform specified actions, before specified time points. When such a real-time process is executed together with other processes with unknown access timing, the unpredictability of resource conflicts with the other processes can make it impossible to guarantee real-time performance, even when it is known that real-time performance is possible, or indeed occurs most of the time.
A number of conflict resolution schemes is known that address real time guarantees. A simple scheme divides time into successive resource access time slots that are assigned to predetermined ones of the processes. If a process issues access requests, the requests will be executed in resource access time slot that are assigned to the process. Effectively, the process “sees” the resource as if it operates at the rate of the assigned time slots. If this visible resource is fast enough, real-time performance of the process can be guaranteed, independent of the behavior of other processes.
Other conflict resolution schemes use arbitration. An arbiter circuit receives the requests from different processes and in each resource access time slot where there is a conflict, the arbiter circuit selects the request of one of the processes and allows that request to be handled. With such an arbiter circuit real-time performance can be guaranteed in various ways, for example by using a variable priority ranking of the processes, so that each process will get highest priority within a predetermined time interval. If the process does not issue a request, a lower priority process will get access instead, so that the resource may be used more frequently.
Such allocation schemes impose limits on the maximum time within which a process will get access to a resource. This guaranteed maximum is independent of other processes. As a result there is also a limit on the maximum delays before real time actions will be performed during execution of the process, provided that the process itself is sufficiently predictable to ensure that no more than certain maximum numbers of execution cycles are needed before the actions are performed.
For processes that are not sufficiently predictable, for example because the number of execution cycles depends on the value of its input data, no such real time guarantees can be given, even if there are limits on the access time. For such processes arbitration schemes that limit the maximum resource access time do not add to predictability. Nevertheless it is desirable that also the timing of such processes is predictable at least in terms of average timing that is averaged over different data inputs.
Unfortunately, real time resource allocation schemes that guarantee only a maximum limit on access time do not have the effect that they make this average timing independent of other processes that are executed concurrently. When there happen to be fewer or more conflicts with other processes the average time will be faster or slower. This speed effect could be removed by including instructions in the programs for performing the processes to wait, if the speed has been too high, but this may unnecessarily decreases progress of the process.